import heapq
from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def maxPerformance(self, n: int, speed: List[int], efficiency: List[int], k: int) -> int:
        people = [[efficiency[i], speed[i]] for i in range(n)]
        people.sort(reverse=True)

        ans = 0

        heap = []
        now = 0
        for e, s in people:
            heapq.heappush(heap, s)
            now += s

            if len(heap) > k:
                now -= heapq.heappop(heap)

            ans = max(ans, now * e)

        return ans % MOD


if __name__ == "__main__":
    print(Solution().maxPerformance(n=6, speed=[2, 10, 3, 1, 5, 8], efficiency=[5, 4, 3, 9, 7, 2], k=2))  # 60
    print(Solution().maxPerformance(n=6, speed=[2, 10, 3, 1, 5, 8], efficiency=[5, 4, 3, 9, 7, 2], k=3))  # 68
    print(Solution().maxPerformance(n=6, speed=[2, 10, 3, 1, 5, 8], efficiency=[5, 4, 3, 9, 7, 2], k=4))  # 72
